 #include"Heap.h"

void HPInit(HP* php)
{
	assert(php);
	php->capacity = 4;
	php->data = (HPDataType*)malloc(sizeof(HPDataType)*4);
	if (php->data == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->size = 0;
}

void AdjustUp(HPDataType* data, int child)
{
	int parent = (child-1)/2;
	while (child>0)
	{
		if (data[child] > data[parent])
		{
			HPDataType tmp = data[child];
			data[child] = data[parent];
			data[parent] = tmp;
			child = parent;
			parent = (child - 1) / 2;
		}
		else break;
	}
}

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType*ptr = (HPDataType*)realloc(php->data,sizeof(HPDataType) * php->capacity * 2);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return;
		}
		else
		{
			php->data = ptr;
			php->capacity *= 2;
		}
	}
	php->data[php->size++] = x;
	AdjustUp(php->data, php->size - 1);
}
void AdjustDown(HPDataType* data,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if ( child+1<n&&data[child + 1] > data[child])child++;
		if (data[child] > data[parent])
		{
			int tmp = data[child];
			data[child] = data[parent];
			data[parent] = tmp;
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	int tmp = php->data[0];
	php->data[0] = php->data[php->size - 1];
	php->data[php->size - 1] = tmp;
	php->size--;
	AdjustDown(php->data, php->size, 0);
}
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size);
	return php->data[0];
}
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
void HPDestroy(HP* php)
{
	assert(php);
	free(php->data);
}